package pers.qianyu.month_202012.date_20201209;

import org.junit.*;

import java.util.*;

/**
 * 773. 滑动谜题
 * https://leetcode-cn.com/problems/sliding-puzzle/
 *
 * @author mizzle rain
 * @date 2020-12-09 17:17
 */
public class SlidingPuzzle {
    public int slidingPuzzle(int[][] board) {
        int[][] right = {{1, 2, 3}, {4, 5, 0}};
        Queue<Node> q = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 0) {
                    Node node = new Node(board, i, j);
                    visited.add(node);
                    q.offer(node);
                    break;
                }
            }
        }
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node node = q.poll();
                if (Arrays.deepEquals(node.board, right)) {
                    return step;
                }
                List<Node> nodes = move(node);
                for (Node n : nodes) {
                    if (!visited.contains(n)) {
                        visited.add(n);
                        q.offer(n);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    private List<Node> move(Node node) {
        int i = node.i;
        int j = node.j;
        int[][] board = node.board;
        List<Node> nodes = new ArrayList<>();
        if (j - 1 >= 0 && j - 1 < 3) {
            int[][] arr = copyArray(board);
            swap(arr, i, j, i, j - 1);
            nodes.add(new Node(arr, i, j - 1));
        }
        if (j + 1 >= 0 && j + 1 < 3) {
            int[][] arr = copyArray(board);
            swap(arr, i, j, i, j + 1);
            nodes.add(new Node(arr, i, j + 1));
        }
        if (i - 1 >= 0 && i - 1 < 2) {
            int[][] arr = copyArray(board);
            swap(arr, i, j, i - 1, j);
            nodes.add(new Node(arr, i - 1, j));
        }
        if (i + 1 >= 0 && i + 1 < 2) {
            int[][] arr = copyArray(board);
            swap(arr, i, j, i + 1, j);
            nodes.add(new Node(arr, i + 1, j));
        }
        return nodes;
    }

    private void swap(int[][] arr, int i, int j, int i1, int j1) {
        int temp = arr[i][j];
        arr[i][j] = arr[i1][j1];
        arr[i1][j1] = temp;
    }

    private int[][] copyArray(int[][] board) {
        int[][] newArray = new int[2][3];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                newArray[i][j] = board[i][j];
            }
        }
        return newArray;
    }

    static class Node {
        // 拼图数组
        public int[][] board;
        // i j 表示 0 的坐标
        public int i;
        public int j;

        public Node(int[][] board, int i, int j) {
            this.board = board;
            this.i = i;
            this.j = j;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node node = (Node) o;

            if (i != node.i) return false;
            if (j != node.j) return false;
            return Arrays.deepEquals(board, node.board);
        }

        @Override
        public int hashCode() {
            int result = Arrays.deepHashCode(board);
            result = 31 * result + i;
            result = 31 * result + j;
            return result;
        }
    }

    @Test
    public void test1() {
        int[][] arr = {{1, 2, 3}, {4, 0, 5}};
        int result = new SlidingPuzzle().slidingPuzzle(arr);
        System.out.println("result = " + result);
    }
}
